import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 周斌
 * Date: 2024-05-06
 * Time: 17:51
 */
public class Main {
    //力扣贪心算法860柠檬水找零
    public boolean lemonadeChange(int[] bills) {
        //记录5元与10元的个数
        int five = 0;
        int ten = 0;
        //遍历这个数组
        for(int x: bills) {
            //5元
            if(x == 5) {
                five++;
            } else if(x == 10)
            //10元
            {
                //手中没有5元,返回fasle
                if(five == 0) {
                    return false;
                } else {
                    five--;
                    ten++;
                }
            }
            //20元
            else {
                //这里体现了贪心，用一个5元+10元还是用3个五元去找零
                if(five != 0 && ten != 0) {
                    five--;
                    ten--;
                }
                else if(five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    //力扣贪心算法2208将数组和减半的最少操作次数
    class Imp implements Comparator<Double> {

        public int compare(Double o1, Double o2) {
            return o2.compareTo(o1);
        }
    }

    class Solution {
        public int halveArray(int[] nums) {
            Imp imp = new Imp();
            // 创建大根堆
            PriorityQueue<Double> heap = new PriorityQueue<>(imp);
            double sum = 0.0;
            int count = 0;
            // 遍历数组，然后将数组的元素放入大根堆中
            for (double x : nums) {
                heap.offer(x);
                sum += x;
            }
            // 将原数组的总和折半
            sum /= 2.0;
            // 通过已经折半的sun来判断 是否已经小于或等于原数组
            while (sum > 0) {
                double tmp = heap.poll() / 2.0;
                sum -= tmp;
                heap.offer(tmp);
                count++;
            }
            return count;
        }
    }
}
